package com.datastructures2.字符串.子字符串查找;

/**
 * Boyer-Moore字符串匹配算法（启发式地处理不匹配的字符）
 * @author MaoLin Wang
 * @date 2020/2/289:29
 */
public class BM {
    private int[] right;
    private String pat;
    public BM(String pat){
        this.pat=pat;
        int R=256;
        this.right=new int[R];
        int M=pat.length();

        for (int i = 0; i < R; i++) {
            right[i]=-1;
        }
        for (int i = 0; i < M; i++) {
            //包含在模式字符串中的值设为其在模式字符串中出现的最后位置
            //如 SELL right[L]=3 right[E]=1
            right[pat.charAt(i)]=i;
        }
    }

    public int search(String txt){
        int N=txt.length();
        int M=pat.length();

        int skip;
        for (int i = 0; i <= N - M; i+=skip) {
            skip=0;
            for (int j = M-1; j >=0 ; j--) {
                if (pat.charAt(j)!=txt.charAt(i+j)){
                    skip = j - right[txt.charAt(i+j)];
                    if (skip<1){
                        skip=1;
                    }
                    break;
                }
            }
            if (skip==0){
                //匹配到了
                return i;
            }
        }
        return N;
    }

    public static void main(String[] args) {
        String text="sadasAfxv";
        BM bm=new BM("Af");
        int search = bm.search(text);
        System.out.println(search);
    }
}
